1. Field of Invention
The present invention relates generally to data communication systems. More particularly, the present invention relates to systems and methods for efficiently routing packets through access points.
2. Description of the Related Art
The demand for data communication services is growing at an explosive rate. Much of the increased demand is due to the fact that as the use of computing devices becomes more prevalent, the need for creating networks of computing devices such that resources may be shared between the computing devices also increases. Typically, wired networks such as local area networks (LANs) are used to enable computing devices within an organization to communicate with each other.
Many organizations which use LANs also use wireless devices that communicate with the LANs. The use of wireless devices such as personal digital assistants (PDAs) and laptop computers enables users of the devices to use the devices in different locations substantially without losing access to computing resources on a LAN. For example, a user of a laptop computer within an organization may use his or her laptop at a first location within a building, then move to a second location within the building. Although the user may physically connect the laptop computer to the LAN using a wired connection at the first and second locations, while the user is “roaming,” or moving, the laptop computer is a roaming device which may not be physically wired to the LAN.
In order to enable roaming devices to communicate with a LAN, access points are used. Access points are arranged to interface with conventional, i.e., wired, LANs in order to effectively create a wireless LAN. FIG. 1 is a diagrammatic representation of a wireless LAN that includes access points. A wireless LAN 100 includes a wired LAN 104 which, as will be appreciated by those skilled in the art, generally includes computing devices such as clients and servers which are networked together in a wired network. LAN 104 is in communication with a router 108 across a connection 112. It should be appreciated, however, that the use of router 108 is optional.
Router 108 is connected to a plurality of access points 116 through wired connections 120. Access points 116 are effectively fixed devices which enable a roaming device 124 to communicate with LAN 104. That is, access points 116 are fixed in desired locations associated with LAN 104 to support communications between roaming device 124 and LAN 104. Access points 116 may be Aironet series access points available from Cisco Systems, Inc., of San Jose, Calif., although it should be understood that access points may be substantially any suitable access points.
Each access point 116 has a corresponding communications range 128. As shown, roaming device 124 is in communications range 128a of access point 116a. In general, the coverage associated with communications range 128a may vary widely. By way of example, communications range 128a may extend to approximately 150 feet in any direction from access point 116a. That is, communications range 128a may have a radius of approximately 150 feet as measured from access point 116a. 
Roaming device 124 communicates with access point 116a in a wireless manner, i.e., using wireless communications, when roaming device 124 is in communications range 128a. Typically, roaming device 124 includes a wireless networking card which enables roaming device 124 to communicate with access points 116. When roaming device 124 is in communications range 128a and attempts to access a resource within LAN 104, e.g., a database within LAN 104, roaming device 124 uses wireless communications to communicate with access point 116a which, in turn, communicates with LAN 104 through wired connections 102a, 104 and router 108, when router 108 is present.
Typically, access points 116 are considered to be bridges or nodes between an Ethernet domain, e.g., LAN 104, and a wireless domain, e.g., roaming device 124. Hence, when a packet is received on an access point 116, access point 116 typically determines how to forward the packet or dispose of the packet. In other words, access point 116 studies the packet to determine what to do with the packet.
With reference to FIG. 2, the processing of packets by an access point will be described. An access point 150 receives packets 160 and determines how to process the received packets 160. Packets 160 may be placed in a packet buffer (not shown) or otherwise queued. In general, while packets 160 may be processed on a first-in-first-out basis, packets 160 may also be prioritized such that packets 160 which include time-sensitive contents may be processed, e.g., processed using quality of service processing, before packets 160 which are not as time-sensitive.
Typically, access point 150 may either forward packets 160 to destinations 170, or dispose of packets 160. By way of example, when access point 150 determines that packet 160c is intended for destination 160b, access point 150 may route or otherwise provide content associated with packet 160c as a part of packet 160c′ to destination 170b. Alternatively, when access point 150 determines that a packet 160 such as packet 160a is to be disposed of, e.g., when packet 160a is a quality of service packet and may not be delivered within a specified amount of time or has expired, access point 150 may dispose of packet 160a by not forwarding packet 160a to a destination 170.
In order to determine an appropriate destination 170 for each packet 160, access point 150 looks at or studies the header of each packet 160. The header of a packet 160, which may be approximately the first twenty-four bits associated with packet 160, includes information which indicates an appropriate destination 170 for packet 160. When access point 150 performs packet filtering to determine whether to forward or dispose of packets 160, access point 150 may either obtain cached information or information that is stored in an associated memory.
FIG. 3 is a diagrammatic representation of a conventional access point, e.g., access point 150 of FIG. 2, that is implemented as a single chip. Access point 150 includes a controller 201 which, in turn, includes processor 202, a data cache (D-cache) 204, an instruction cache (I-cache) 206, and a cache controller 208. D-cache 204 is arranged to cache data, while I-cache 206 is arranged to cache instructions. Processor 202, which may be a RISC central processing unit (CPU) or substantially any other type of CPU, may obtain an instruction from each of D-cache 204 and I-cache 206 with each clock cycle, as will be understood by those skilled in the art. Cache controller 208 may be associated with tags, which are held in a tag random access memory (RAM), and identify translations that are stored in external memory. In other words, tags identify address locations in external memory such that controller 201 may access appropriate locations within the external memory through external memory interface 212. Such appropriate locations may include storage locations which store information associated with a particular packet that is being processed.
A local bus 210 is arranged to facilitate the transfer of information between an external memory interface 212 of access point 150, an Ethernet interface 214 of access point 150, and caches 204, 206. External memory interface 212 is arranged to allow access point 150 to interface with an external memory such as a shared global memory in order to obtain translations used to substantially interpret the contents of headers of packets. Ethernet interface 214 is arranged to enable packets to be received from an external network and forwarded through the external network.
Information is often stored in caches 204, 206 because accessing information stored in external memory through external memory interface 212 is often time-consuming and expensive. D-cache 204, for example, may store header information such as a packet header, and mappings or translations which have recently been accessed with regards to processing packet headers. When a suitable mapping for a given packet is available in D-cache 204, processing the packet or, more particularly, the packet header may occur efficiently and with relatively low overhead, e.g., without accessing external memory or causing the main D-cache 204 to be updated.
Space within D-cache 204, however, is generally limited and, hence, is often cleared when software executing on processor 202 accesses other variables or data. In other words, packet headers or mappings may often be cleared from D-cache 204 such that when a packet header or a mapping that was previously in D-cache 204 is once again needed, the mapping must either be recreated or obtained from external memory. A process known as thrashing may occur when information that is needed is not available within D-cache 204. As will be appreciated by those skilled in the art, thrashing typically occurs when information is not available within D-cache 204, and an external memory is accessed to obtain the information which is then loaded into D-cache 204.
Further, D-cache 204 is often not coherent with respect to Ethernet packets. Cache coherence, as will be appreciated by those skilled in the art, typically means that cache control hardware tracks the accesses that a CPU makes within its address space. If the CPU attempts to access a location in memory, of the memory is marked as cachable, then the cache controller will typically update the cache line, i.e., a small block of cache whose size is typically aligned with the burst capabilities of a DRAM subsystem, that contains that location in the memory space. Hence, as a CPU operates, the cache is read and updated out of the system DRAM, or the cache is copied back out to the DRAM if the CPU has modified the variables in the cache. This is typically done automatically by the cache controller hardware. No intervention of the CPU is generally required for this to work properly, but all accesses to the system DRAM typically must be tracked by the cache controller. To keep processor speed substantially maximized, most variables and code are defined as cachable. As a result, most accesses to the external DRAM are cache updates, an indirect result of the current access of the CPU, and not the CPU directly accessing external memory.
When an Ethernet packet is received, the Ethernet packet is copied to the DRAM via an internal bus which uses bus mastering DMA. This is generally done without direct interaction from the main CPU. It may is typically also done without the knowledge of the cache controller. As a result, the Ethernet packet is generally not cache coherent because the system cache controller does not have knowledge of a variable update. If a variable is to be cached, as the variable generally will be if the variable is to be used more than once, the variable must be updated. When the CPU has a variable, e.g., an Ethernet header, that is not cache coherent but that the CPU wants cached, the CPU may manually force the cache controller to update that variable each time the CPU believes that the variable may be changed. Such updating is inefficient and uses substantially overhead on a main CPU, and effectively wastes CPU cycles.
Efficiently enabling packets to be routed through an access point is important to the performance of the access point, as well as the performance of the overall network which includes the access point. When packets are not processed efficiently, the speed associated with the overall network may be compromised. For example, as discussed above, when information associated with a packet header of a packet such as mapping information is not available in a data cache, the information may be obtained from an external memory, which requires a significant amount of overhead and is time-consuming. The delay associated with obtaining the information from the external memory, and loading the information into the data cache, may cause undesirable delays in forwarding the packet to a desired destination.
Therefore, what is needed is a system and a method for efficiently filtering packets received on an access point. That is, what is desired is a system and a method for efficiently caching information associated with a packet header such that needed information is substantially always available in a cache.